/*
 * @Author: your name
 * @Date: 2024-04-02 10:26:43
 * @LastEditTime: 2024-04-02 10:35:10
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\142.环形链表-ii.cpp
 */
/*
 * @lc app=leetcode.cn id=142 lang=cpp
 *
 * [142] 环形链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* flag1 = nullptr;
        ListNode* flag2 = nullptr;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                flag1 = fast;
                flag2 = head;
                while(flag1 != flag2){
                    flag1 = flag1->next;
                    flag2 = flag2->next;

                }
                return flag1;
            }
        }
        return nullptr;
    }
};
// @lc code=end

